import java.util.ArrayList;
import java.util.Arrays;

public class JianZhiOffer_SumEqualsS {
    public static void main(String[] args) {
        System.out.println(FindNumbersWithSum(new int[]{1,2,4,7,11,15}, 15));
    }
    public static ArrayList<Integer> FindNumbersWithSum(int [] array,int sum) {
        ArrayList<Integer> list = new ArrayList<>();
        if (array.length == 0 || array.length == 1) {
            return list;
        }
        Arrays.sort(array);
        int p = array.length - 1;
        while (array[p] >= sum) {
            p--;
        }

        if (p == 0) {
            return list;
        }

        while (p >= 1) {
            int left = 0;
            int right = p - 1;
            if (array[right] + array[p] < sum) {
                return list;
            }
            if (array[left] + array[p] > sum) {
                p--;
                continue;
            }
            while (left <= right) {
                if (array[left] + array[p] < sum) {
                    left++;
                }
                if (array[right] + array[p] > sum) {
                    right--;
                }
                if (array[left] + array[p] == sum) {
                    list.add(array[left]);
                    list.add(array[p]);
                    return list;
                }
                if (array[right] + array[p] == sum) {
                    list.add(array[right]);
                    list.add(array[p]);
                    return list;
                }
            }
            p--;
        }

        return list;
    }

    public int[] twoSum(int[] price, int target) {
        int[] arr = new int[2];
        int left = 0;
        int right = price.length - 1;
        while (left < right) {
            if (price[left] + price[right] > target) {
                right--;
            } else if (price[left] + price[right] < target) {
                left++;
            } else {
                arr[0] = price[left];
                arr[1] = price[right];
                return arr;
            }
        }

        return arr;
    }
}
